﻿// Write a program that sorts an array of strings using the quick sort algorithm (find it in Wikipedia).

using System;

class QuickSortArray
{
    static void Main()
    {
        // read Array Size
        uint arraySize;
        do
        {
            Console.Write("Enter sorted array size: ");
        } while (!uint.TryParse(Console.ReadLine(), out arraySize));

        // read array elements
        int[] intArray = new int[arraySize];
        for (int i = 0; i < intArray.Length; i++)
        {
            do
            {
                Console.Write("Enter array elements {0}: ", i + 1);
            } while (!int.TryParse(Console.ReadLine(), out intArray[i]));
        }

        // quick sort
        QuickSortArrayRecursive(intArray, 0, intArray.Length - 1);

        // print sorted array
        Console.Write("Sorted Array: {");
        for (int i = 0; i < intArray.Length; i++)
        {
            Console.Write(intArray[i]);
            if (i != intArray.Length - 1)
            {
                Console.Write(", ");
            }
        }
        Console.WriteLine("}");
    }

    private static void QuickSortArrayRecursive(int[] intArray, int left, int right)
    {
        if (intArray == null || intArray.Length == 1)
        {
            return;
        }

        int i = left;
        int j = right;
        // calc middle marker
        int pivot = (left + right) / 2;

        while (i <= j)
        {
            while (intArray[i] < intArray[pivot])
            {
                i++;
            }

            while (intArray[j] > intArray[pivot])
            {
                j--;
            }

            if (i <= j)
            {
                // exchange elements with index i and j
                int tempElement = intArray[i];
                intArray[i] = intArray[j];
                intArray[j] = tempElement;
                // move markers to the middle
                i++;
                j--;
            }
        }

        if (j > left)
        {
            // run the same method again for left side
            QuickSortArrayRecursive(intArray, left, j);
        }
        if (i < right)
        {
            // run the same method again for right side
            QuickSortArrayRecursive(intArray, i, right);
        }
    }
}